/*
 * @lc app=leetcode.cn id=105 lang=cpp
 *
 * [105] 从前序与中序遍历序列构造二叉树
 */
#include <iostream>
#include <unordered_map>
#include <vector>
using std::vector;
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution
{
  private:
    std::unordered_map<int, TreeNode *> val_to_node;
    /* 记录对应节点的值，在中序遍历中的位置 */
    std::unordered_map<int, int> val_to_index;
    /* pre_left表示前序序列的起点，in_left表示中序遍历的左边界，right表示中序遍历的右边界，闭区间 */
    TreeNode *build_helper(vector<int> &preorder, vector<int> &inorder, int pre_left, int in_left, int in_right)
    {
        if (pre_left > preorder.size() || in_left > in_right) {
            return nullptr;
        }

        TreeNode *root = nullptr;
        if (!val_to_node.count(preorder[pre_left])) {
            root = val_to_node[preorder[pre_left]] = new TreeNode(preorder[pre_left]);
        } else {
            root = val_to_node[preorder[pre_left]];
        }
        std::cout << "root的值为 " << root->val << std::endl;
        int root_in_inorder_index = val_to_index[root->val];
        int left_subtree_size = root_in_inorder_index - in_left;
        int right_subtree_size = in_right - root_in_inorder_index;

        root->left = build_helper(preorder, inorder, pre_left + 1, in_left, root_in_inorder_index - 1);
        root->right = build_helper(preorder, inorder, pre_left + 1 + left_subtree_size, root_in_inorder_index + 1, in_right);
        return root;
    }

  public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder)
    {
        int size = inorder.size();
        for (int i = 0; i < size; i++) {
            val_to_index[inorder[i]] = i;
        }
        return build_helper(preorder, inorder, 0, 0, size - 1);
    }
};
// @lc code=end